#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// 铺地砖
#if 0
// dp[1] = 1
// dp[2] = 2
// dp[3] = 4
// dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

int dp[51] = {0};
int main()
{
    int t = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i < 51; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    scanf("%d", &t);
    int n = 0;
    while (t--)
    {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
    return 0;
}
#endif
// 炫耀手机
#if 0
// dp[1] = 0
// dp[2] = 5
// dp[i] = dp[i-1]*4+dp[i-2]*5
long long dp[21] = {0};
int main()
{
    dp[1] = 0;
    dp[2] = 5;
    for (int i = 3; i < 21; ++i)
    {
        dp[i] = dp[i - 1] * 4 + dp[i - 2] * 5;
    }
    int n = 0;
    while (scanf("%d", &n) != EOF)
    {
        printf("%lld\n", dp[n]);
    }
    return 0;
}
#endif
// 切煎饼
#if 0
// 递推公式 dp[i] = dp[i-1]+2*(n-1)
int dp[200] = {0};
int main()
{
    dp[0] = 0;
    dp[1] = 2;
    for (int i = 2; i < 200; ++i)
    {
        dp[i] = dp[i - 1] + i;
    }
    int n = 0;
    while (scanf("%d", &n) != EOF)
    {
        printf("%d\n", dp[n]);
    }
    return 0;
}
#endif
// 平面划分
#if 0
// 递推公式 D(i) = D(i-1)+2*(i-1)
long long dp[1000] = {0};
int main()
{
    dp[0] = 1;
    dp[1] = 2;

    for (int i = 2; i < 1000; ++i)
    {
        dp[i] = dp[i - 1] + 2 * (i - 1);
    }
    int n = 0;
    while (scanf("%d", &n) != EOF)
    {
        printf("%d\n", dp[n]);
    }
    return 0;
}
#endif
// 隔离区
#if 0
// 关键是 取点 取N-2个点
// 他产生的边数依次为 2 3 4 5 ...
// 而另外一边产生的则是 N-2+1 N-3+1 N-4+1 N-5+1 ...
int result[21] = {0};
int func(int n)
{
    if (n == 2 || n == 3)
        return 1;
    if (result[n])
        return result[n];
    for (int i = 2; i < n; ++i)
        result[n] += (func(i) * func(n - i + 1));
    return result[n];
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", func(n));
    return 0;
}
#endif
// 实验室的书
#if 0
// 错排问题
// D(n)为n本书的错排
// 对于n本书中的一本 如果将其拿起放在位置为k的位置上
// 那么 首先这本书有 n-1 个位置可以放
// 其次 对于那本k位置上的书:
// 1. 放在n的位置上, D(n-2)种结果
// 2. 放在非n的位置上, 相当于n-1本书中, 拿起一本书, D(n-1)种结果
// D(n) = (n-1)*[D(n-1) + D(n-2)]
// D(0) = 0 D(1) = 0 D(2) = 1

int main()
{
    long long data[21] = {0};
    data[0] = data[1] = 0;
    data[2] = 1;
    for (int i = 3; i < 21; ++i)
    {
        data[i] = (i - 1) * (data[i - 1] + data[i - 2]);
    }
    int n = 0;
    scanf("%d", &n);
    printf("%lld\n", data[n]);
    return 0;
}
#endif
// 礼品分组
#if 0
// 枚举最大值即可, 但是不要忘记中间的那一个
int compare(const void *a, const void *b)
{
    return *(int *)a > *(int *)b;
}

int main()
{
    int max = 0;
    int n = 0;
    int data[30000] = {0};
    int result = 0;
    scanf("%d %d", &max, &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", data + i);
    }
    qsort(data, n, sizeof(int), compare);
    int left = 0;
    int right = n - 1;
    while (data[right] >= max)
    {
        ++result;
        --right;
    }
    while (left < right)
    {
        if (data[left] + data[right] > max)
        {
            --right;
            ++result;
        }
        else
        {
            ++result;
            ++left;
            --right;
        }
    }
    if (left == right)
        ++result;
    printf("%d\n", result);
    return 0;
}
#endif
// 三只小猪
#if 0
int main()
{

    int n = 0;
    int m = 0;
    // 假设分配方案为 ways[n][m]
    // n为猪的个数 m为房子的个数
    // 对于每一个猪 有两种选择:
    // 1. 和别的猪一起住, 则方案为 m*ways[n-1][m] (m个房子可以住)
    // 2. 自己一个人住, 则方案为 ways[n-1][m-1]
    // 即 ways[n][m] = m*ways[n-1][m] + ways[n-1][m-1]

    long long ways[21][21] = {0};
    for (int i = 0; i < 21; ++i)
    {
        for (int j = 0; j < 21; ++j)
        {
            if (i == j)
                ways[i][j] = 1;
            else if (i < j)
                ways[i][j] = 0;
            else
            {
                if (j == 0)
                    ways[i][j] = 0;
                else
                    ways[i][j] = j * ways[i - 1][j] + ways[i - 1][j - 1];
            }
        }
    }
    while (scanf("%d %d", &n, &m) != EOF)
    {
        printf("%lld\n", ways[n][m]);
    }
    return 0;
}
#endif
// 链表删除数据
#if 0
int main()
{
    int data[2000000] = {0};
    int n = 0;
    while (scanf("%d", &n) != EOF)
    {
        if (n == 0)
            printf("list is empty\n");
        else
        {
            for (int i = 0; i < n; ++i)
            {
                scanf("%d", data + i);
            }
            for (int i = 0; i < n; ++i)
            {
                printf("%d ", data[i]);
            }
            printf("\n");
            int pre = data[0];
            printf("%d ", pre);
            for (int i = 1; i < n; ++i)
            {
                if (data[i] != pre)
                {
                    printf("%d ", data[i]);
                    pre = data[i];
                }
            }
            printf("\n");
        }
    }
    return 0;
}
#endif
// 相同字符串
#if 1
char ans[30001];
char buf[30001];

int main()
{
    char s[30001] = {0};
    scanf("%s", &s);
    int slen = strlen(s);
    int i = 0;
    int len = 0;
    char *sptr = NULL;
    ans[0] = '\0';
    while (i + len < slen)
    {
        memcpy(buf, s + i, sizeof(char) * len);
        buf[len] = '\0';
        sptr = strstr(s + i + 1, buf);
        if (sptr)
        {
            while (sptr[len] != 0 && sptr[len] == s[i + len])
            {
                buf[len] = sptr[len];
                ++len;
            }
            buf[len] = 0;
            strcpy(ans, buf);
            ++len;
        }
        else
        {
            ++i;
        }
    }
    printf("%s\n%d\n", ans, 1 + (int)(s - strstr(s, ans)));
    return 0;
}
#endif
// 进制转换
#if 0
const char *key = "0123456789ABCDEF";
void trans(int n, int base, char a[])
{
    int num = 0;
    while (n)
    {
        a[num++] = key[n % base];
        // printf("%c\n", a[num++]);
        n /= base;
    }
    int left = 0;
    int right = num - 1;
    char tmp = 0;
    while (left < right)
    {
        tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
        ++left;
        --right;
    }
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    char num[3][30] = {0};
    trans(n, 2, num[0]);
    trans(n, 8, num[1]);
    trans(n, 16, num[2]);
    printf("%s\n%s\n%s\n", num[0], num[1], num[2]);
    return 0;
}
#endif
// 人工智能
#if 0
typedef struct Info
{
    char com[15];
    char name[25];
    float value;
} Info;

int compare(const void *a, const void *b)
{
    return ((Info *)a)->value <= ((Info *)b)->value;
}

int main()
{
    int t = 0;
    scanf("%d", &t);
    Info info[25];
    while (t--)
    {
        int n = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%s", info[i].com);
        for (int i = 0; i < n; ++i)
            scanf("%s", info[i].name);
        for (int i = 0; i < n; ++i)
            scanf("%f", &(info[i].value));
        qsort(info, n, sizeof(Info), compare);
        for (int i = 0; i < n; ++i)
            printf("%s %s %.2f\n", info[i].com, info[i].name, info[i].value);
    }
    return 0;
}
#endif